package com.lzhsite.leetcode.algoritom.practise.arrays;

/*
 有个长度为 2n 的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，
 希望排序后{a1,b1,a2,b2,....,an,bn}，请
考虑有无时间复杂度 o(n)，空间复杂度 0(1)的解法
*/
public class 洗牌算法 {

	 /* 仔细观察变换前后两个序列的特点，我们可做如下一系列操作：
		第①步、确定 b1 的位置，即让 b1 跟它前面的 a2， a3， a4 交换：
		a1， b1， a2， a3， a4， b2， b3， b4
		第②步、接着确定 b2 的位置，即让 b2 跟它前面的 a3， a4 交换：
		a1， b1， a2， b2， a3， a4， b3， b4第③步、 b3 跟它前面的 a4 交换位置：
		a1， b1， a2， b2， a3， b3， a4， b4
		b4 已在最后的位置，不需要再交换。如此，经过上述 3 个步骤后，得到我们最后想要的序列。
		但此方法的时间复杂度为 O（ N^2），我们得继续寻找其它方法，看看有无办法能达到题目所预
		期的 O（ N）的时间复杂度
		*/
		
		
	  /*为方便讨论，我们设定数组的下标从 1 开始，下标范围是[1..2n]。 还是通过之前 n=4 的例子，
		来看下每个元素最终去了什么地方。
		起始序列： a1 a2 a3 a4 b1 b2 b3 b4 数组下标： 1 2 3 4 5 6 7 8 最终序列： b1 a1 b2 a2 b3 a3 b4
		a4
		从上面的例子我们能看到，前 n 个元素中，
		第 1 个元素 a1 到了原第 2 个元素 a2 的位置，即 1->2；第 2 个元素 a2 到了原第 4 个元素 a4 的位置，即 2->4；
		第 3 个元素 a3 到了原第 6 个元素 b2 的位置，即 3->6；
		第 4 个元素 a4 到了原第 8 个元素 b4 的位置，即 4->8；
		那么推广到一般情况即是：前 n 个元素中，第 i 个元素去了 第（ 2 * i）的位置。
		上面是针对前 n 个元素，那么针对后 n 个元素，可以看出：
		第 5 个元素 b1 到了原第 1 个元素 a1 的位置，即 5->1；
		第 6 个元素 b2 到了原第 3 个元素 a3 的位置，即 6->3；
		第 7 个元素 b3 到了原第 5 个元素 b1 的位置，即 7->5；
		第 8 个元素 b4 到了原第 7 个元素 b3 的位置，即 8->7；
		推广到一般情况是，后 n 个元素，第 i 个元素去了第 (2 * (i - n) ) - 1 = 2 * i - (2 * n + 1) = (2 * i) %
		(2 * n + 1) 个位置。
		再综合到任意情况，任意的第 i 个元素，我们最终换到了 (2 * i) % (2 * n + 1)的位置。为何呢？
		因为：
		当 0 < i < n 时， 原式= (2i) % (2 * n + 1) = 2i；
		当 i > n 时，原式(2 * i) % (2 * n + 1)保持不变。
		因此，如果题目允许我们再用一个数组的话，我们直接把每个元素放到该放得位置就好了。也就
		产生了最简单的方法 pefect_shuffle1，参考代码如下：*/
		
		// 时间 O(n)，空间 O(n) 数组下标从 1 开始
		void pefectShuffle1(String a[], int n) {
			int n2 = n * 2, i;
			String[] b = new String[n2+1];
			for (i = 1; i <= n2; ++i) {
				b[(i * 2) % (n2 + 1)] = a[i];
				System.out.print((i * 2) % (n2 + 1)+"("+i+") ");
			}
			for (i = 1; i <= n2; ++i) {
				a[i] = b[i];
			}
		}
		public static void main(String[] args) {
			int n=4;
			String arr[]=new String[2*n+1];
			for (int i = 1; i <= 2*n; i++) {
				arr[i]= (i<=n? "a":"b")+ (i-1)%n+1;
			}
			new 洗牌算法().pefectShuffle1(arr,n);
		}

	/*
	 但很明显，它的时间复杂度虽然是 O(n)，但其空间复杂度却是 O(n)，仍不符合本题所期待的时
	间 O(n)，空间 O(1)。我们继续寻找更优的解法。
	与此同时，我也提醒下读者，根据上面变换的节奏，我们可以看出有两个圈，
	一个是 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1；
	一个是 3 -> 6 -> 3
	*/
		
	 
	/*	
	 * 这两个圈可以表示为（ 1,2,4,8,7,5）和（ 3,6），且 perfect_shuffle1 算法也已经告诉了我们，不
		管你 n 是奇数还是偶数，每个位置的元素都将变为第（ 2*i） % （ 2n+1）个元素：
		因此我们只要知道圈里最小位置编号的元素即圈的头部，顺着圈走一遍就可以达到目的，且因为
		圈与圈是不相交的，所以这样下来，我们刚好走了 O（ N）步。
		还是举 n=4 的例子，且假定我们已经知道第一个圈和第二个圈的前提下，要让 1 2 3 4 5 6 7 8
		变换成 5 1 6 2 7 3 8 4：第一个圈： 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1 第二个圈： 3 -> 6 -> 3：
		原始数组： 1 2 3 4 5 6 7 8 数组下标： 1 2 3 4 5 6 7 8
		走第一圈： 5 1 3 2 7 6 8 4 走第二圈： 5 1 6 2 7 3 8 4
		上面沿着圈走的算法我们给它取名为 cycle_leader，这部分代码如下：
		//数组下标从 1 开始， from 是圈的头部， mod 是要取模的数 mod 应该为 2 * n +
		1，时间复杂度 O(圈长）
		*/
	
	void CycleLeader(int a[], int from, int mod) {
		int t, i;
		for (i = from * 2 % mod; i != from; i = i * 2 % mod) {
			t = a[i];
			a[i] = a[from];
			a[from] = t;
		}
	}
}
